﻿#define _CRT_SECURE_NO_WARNINGS

#include"Graph.h"

//邻接矩阵的创建
void CreateDUN(AMGraph* G)
{
	printf("输入总顶点数、总边数：");
	scanf("%d %d", &(G->vexnum), &(G->arcnum));
	getchar();

	int i = 0;
	int j = 0;
	//初始化邻接矩阵
	for (i = 0; i < G->vexnum; i++)
		for (j = 0; j < G->vexnum; j++)
			G->arcs[i][j] = MaxINt;

	printf("依次输入各边的信息：");
	//依次输入各顶点的信息
	for (i = 0; i < G->vexnum; i++)
		scanf(" %c", &(G->vexs[i]));
	getchar();

	VerTexType v1, v2;			//一条边依附的两个顶点
	ArcType M;					//这条边的权值
	for (i = 0; i < G->arcnum; i++)
	{
		printf("输入边依附的两个点和其权值：");
		scanf("%c %c %d", &v1, &v2, &M);
		getchar();
		//获取点在图中的位置（下标）
		int pos1 = LocateVex(G, v1);
		int pos2 = LocateVex(G, v2);
		G->arcs[pos1][pos2] = M;
		G->arcs[pos2][pos1] = G->arcs[pos1][pos2]; //无向图邻接矩阵关于对角线对称
 	}
}

//打印邻接矩阵
void PrintArc(AMGraph* G)
{
	int i = 0;
	int j = 0;
	for (i = 0; i < G->vexnum; i++)
	{
		for (j = 0; j < G->vexnum; j++)
			printf("%-5d ", G->arcs[i][j]);
		printf("\n");
	}
}

//获取点的位置
int LocateVex(AMGraph* G, VerTexType x)
{
	int i = 0;
	for (i = 0; i < G->vexnum; i++)
	{
		if (x == G->vexs[i])
			return i;
	}

	printf("找不到\n");
	exit(0);
}

//创建辅助数组Edge
Auxiliary* Creat_Edge(AMGraph* G)
{
	//注意一下内存泄漏
	Auxiliary* temp = (Auxiliary*)malloc(sizeof(Auxiliary) * G->arcnum);
	if (!temp)
	{
		perror("malloc");
		exit(-1);
	}
	Auxiliary* Edge = temp;

	int i;
	int j;
	int k = 0;			//控制Edge数组的下标


	for (i = 1; i < G->vexnum; i++)
	{
		for (j = 0; j < i; j++)
		{
			if (G->arcs[i][j] != MaxINt)
			{
				Edge[k].Head = G->vexs[i];
				Edge[k].Tail = G->vexs[j];
				Edge[k].lowcost = G->arcs[i][j];
				k++;
			}
		}
	}
	
	return Edge;
}

//创建辅助数组Vexset
int* Creat_Vexset(AMGraph* G)
{
	int* tmp = (int*)malloc(sizeof(int) * G->vexnum);
	if (!tmp)
	{
		perror("malloc");
		exit(-1);
	}
	int* Vexset = tmp;

	//表示各顶点自成一个连通分量
	int i = 0;
	for (i = 0; i < G->vexnum; i++)
	{
		//每一个下标对应顶点表中一个顶点的下标
		Vexset[i] = i;
	}
	return Vexset;
}

//提供比较函数
int cmp_int(const void* p1, const void* p2)
{
	return ((Auxiliary*)p1)->lowcost - ((Auxiliary*)p2)->lowcost;		//p1 - p2，排升序
}

//克鲁斯卡尔算法
//无向网G以邻接矩阵形式存储，构造G的最小生成树T，输出T的各条边
MiniSpanTree_Kruskal(AMGraph* G)
{
	//获得辅助数组Edge，同时初始化数组
	//注意内存泄漏
	Auxiliary* Edge = Creat_Edge(G);
	
	//我们的无向图，是一个简化的无向图，一个没有回路，没有双路的图
	int size = G->arcnum;				//Edge数组的元素个数
	qsort(Edge, size, sizeof(Auxiliary), cmp_int);

	//获得辅助数组Vexset
	int* Vexset = Creat_Vexset(G);

	//依次查看数组Edge中的边
	int i = 0;
	for (i = 0; i < G->arcnum; i++)
	{
		int v1 = LocateVex(G, Edge[i].Head);	//v1为边的始点Head的下标
		int v2 = LocateVex(G, Edge[i].Tail);	//v2为边的终点Tail的下标
		int vs1 = Vexset[v1];					//获取边Edge[i]的始点所在的连通分量vs1
		int vs2 = Vexset[v2];					//获得边Edge[i]的终点所在的连通分量vs2
		if (vs1 != vs2)
		{
			printf("%c -- %c\n", Edge[i].Head, Edge[i].Tail);	//输出此边
			int j = 0;
			//合并vs1和vs2两个连通分量，即两个集合统一编号
			for (j = 0; j < G->vexnum; j++)
				if (Vexset[j] == vs2)
					Vexset[j] = vs1;			//集合编号为vs2的都改为vs1
		}
	}

	//释放内存，避免内存泄漏
	free(Edge);
	Edge = NULL;
	free(Vexset);
	Vexset = NULL;
}